Additively separable hedonic games and fractional hedonic games have receivedconsiderable attention. They are coalition forming games of selfish agentsbased on their mutual preferences. Most of the work in the literaturecharacterizes the existence and structure of stable outcomes (i.e., partitionsin coalitions), assuming that preferences are given. However, there is littlediscussion on this assumption. In fact, agents receive different utilities ifthey belong to different partitions, and thus it is natural for them to declaretheir preferences strategically in order to maximize their benefit. In thispaper we consider strategyproof mechanisms for additively separable hedonicgames and fractional hedonic games, that is, partitioning methods withoutpayments such that utility maximizing agents have no incentive to lie abouttheir true preferences. We focus on social welfare maximization and provideseveral lower and upper bounds on the performance achievable by strategyproofmechanisms for general and specific additive functions. In most of the cases weprovide tight or asymptotically tight results. All our mechanisms are simpleand can be computed in polynomial time. Moreover, all the lower bounds areunconditional, that is, they do not rely on any computational or complexityassumptions.
展开▼
